struct Stoer_Wagner {
    static const int N=506, INF=(1<<30);
    int G[N][N], W[N], Merge[N], S, T, minCut, n, vs[N];

    void init(int _n) {
        n=_n;
        memset(G, 0, sizeof G);
    }
    void BFS() {
        memset(vs, 0, sizeof vs);
        memset(W, 0, sizeof W);
        S=T=-1;
        int Max, id;
        for(int cnt=0; cnt<n; cnt++) {
            Max=-INF;
            for(int i=0; i<n; i++)
                if(!Merge[i] && !vs[i] && W[i]>Max)
                    Max=W[i], id=i;
            if(id==T) return;
            S=T, T=id, minCut=Max;
            vs[id]=1;
            for(int i=0; i<n; i++) {
                if(Merge[i] || vs[i]) continue;
                W[i]+=G[id][i];
            }
        }
    }
    int StoerWagner() {
        memset(Merge, 0, sizeof Merge);
        int ans=INF;
        for(int cnt=1; cnt<n; cnt++) {
            BFS();
            if(minCut<ans) ans=minCut;
            if(ans==0) return ans;
            Merge[T]=1;
            for(int i=0; i<n; i++) {
                if(Merge[i]) continue;
                G[S][i]+=G[T][i];
                G[i][S]+=G[i][T];
            }
        }
        return ans;
    }
};
